package DivideAndConquer;

import java.util.ArrayList;
import java.util.List;

public class _241_DifferentWaystoAddParentheses {
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (c == '+' || c == '-' || c == '*') {
                String part1 = input.substring(0, i);
                String part2 = input.substring(i + 1);
                List<Integer> part1sets = diffWaysToCompute(part1);
                List<Integer> part2sets = diffWaysToCompute(part2);
                for (int a : part1sets) {
                    for (int b : part2sets) {
                        if (c == '+') {
                            res.add(a + b);
                        } else if (c == '-') {
                            res.add(a - b);
                        } else {
                            res.add(a * b);
                        }
                    }
                }
            }
        }
        if(res.size()==0) res.add(Integer.valueOf(input));
        return res;
    }
}
